package primeNumbers;

import java.util.Arrays;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Semaphore;

public class EratosthenesSieve {

	private int threads;
	private boolean[] isPrime;
	private BlockingQueue<Job> jobs;
	private Semaphore semaphore;
	private ExecutorService executor;

	private class Job {
		public int from, to, step;

		public Job(int from, int to, int step) {
			this.from = from;
			this.to = to;
			this.step = step;
		}
	}

	private class Worker implements Runnable {
		@Override
		public void run() {
			while (true) {
				Job job;
				try {
					job = jobs.take();
					if (job.to == 0)
						return;
					while (job.from % job.step != 0)
						job.from++;
					for (int i = job.from; i <= job.to; i += job.step)
						isPrime[i] = false;
					semaphore.release();
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
	}

	public EratosthenesSieve(int upperBound, int threads) {
		if (threads < 1)
			throw new IllegalArgumentException(
					"There has to be at least 1 thread");
		if (upperBound < 2)
			throw new IllegalArgumentException(
					"There are no prime numbers less than 2");
		this.threads = threads;
		isPrime = new boolean[upperBound + 1];
		Arrays.fill(isPrime, true);
		isPrime[0] = false;
		isPrime[1] = false;
		jobs = new ArrayBlockingQueue<Job>(threads);
		semaphore = new Semaphore(threads);
		executor = Executors.newFixedThreadPool(threads);
	}

	private void runEratosthenesSieve() {
		int upperBound = isPrime.length - 1;
		int upperBoundSquareRoot = (int) Math.sqrt(upperBound);
		for (int thread = 0; thread < threads; thread++) {
			executor.submit(new Worker());
		}
		for (int factor = 2; factor <= upperBoundSquareRoot; factor++) {
			if (isPrime[factor]) {
				for (int threadNumber = 1; threadNumber <= threads; threadNumber++) {
					int from;
					if (threadNumber == 1) {
						from = factor * factor;
					} else {
						from = (threadNumber - 1) * upperBound / threads;
					}
					Job job = new Job(from,
							threadNumber * upperBound / threads, factor);
					try {
						jobs.put(job);
					} catch (InterruptedException e) {
						e.printStackTrace();
					}
				}
				try {
					semaphore.acquire(threads);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
		}
		for (int i = 0; i < threads; i++) {
			try {
				jobs.put(new Job(0, 0, 0));
			} catch (InterruptedException e) {
				e.printStackTrace();
			}
		}
		executor.shutdown();
	}

	private int getNumberOfPrimes() {
		int numberOfPrimes = 0;
		for (boolean numberIsPrime : isPrime)
			if (numberIsPrime)
				numberOfPrimes++;
		return numberOfPrimes;
	}

	public int[] getAllPrimes() {
        runEratosthenesSieve();
		int[] primeNumbers = new int[getNumberOfPrimes()];
		int nextPrimeIndex = 0;
		for (int number = 1; number < isPrime.length; number++)
			if (isPrime[number]) {
				primeNumbers[nextPrimeIndex] = number;
				nextPrimeIndex++;
			}
		return primeNumbers;
	}
}